package jun;

import java.util.*;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-6-23 10:37
 * @description：
 * @modified By：
 * @version:
 */
public class Jun23 {
    private int j = 20;
    public static List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        /**
         * create by: 冯涛滔
         * description: https://leetcode-cn.com/problems/robot-in-a-grid-lcci/submissions/ 面试题 08.02. 迷路的机器人
         * 每个格子记录可以走到这个格子的一种可能 一直记录到右下角
         * create time: 2020-6-23 11:41
         * @params [obstacleGrid]
         * @return java.util.List<java.util.List < java.lang.Integer>>
         */
        List<List<Integer>> res = new ArrayList<>();
        //初始化好两边
        if(obstacleGrid[0][0]==1)
            return res;
        int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length]; //1左边 2就上 0就是死路
        dp[0][0] = 2;
        for (int i = 1; i < obstacleGrid[0].length; i++) {
            if (dp[0][i-1]!=0&&obstacleGrid[0][i]!=1) {
                dp[0][i] = 1;
            }
        }
        for (int i = 1; i < obstacleGrid.length; i++) {
            if (dp[i-1][0]!=0&&obstacleGrid[i][0]!=1) {
                dp[i][0] = 2;
            }
        }
        for (int i = 0; i < obstacleGrid.length; i++) {
            for (int j = 0; j < obstacleGrid[i].length; j++) {
                if(obstacleGrid[i][j]==1){
                    dp[i][j]=0;
                    continue;
                }
                if(i==0||j==0){
                    if(obstacleGrid[i][j]==1){
                        dp[i][j]=0;
                    }
                    continue;
                }
                if(dp[i-1][j]!=0){
                    dp[i][j] = 2;//上
                }else{
                    if(dp[i][j-1]!=0){
                        dp[i][j] = 1; //左
                    }
                }
            }
        }
        if(dp[obstacleGrid.length-1][obstacleGrid[0].length-1]==0)
            return res;
        int i = dp.length-1;
        int j = dp[i].length-1;
        while(i!=-1){
            res.add(0,Arrays.asList(i, j));
            if(dp[i][j]==1){//上一步是左边
                j--;
                continue;
            }
            if(dp[i][j]==2){//上一步是上边
                i--;
            }
        }
        return  res;
    }

    public static void main(String[] args) {
        int[][] a= {{0,0}};
        System.out.println(pathWithObstacles(a));
    }
}
